SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Dual linear program</title>

</head>

Dual linear program

</h1>

</header>

The dual of a given <a href="Linear_program" class="mw-redirect" title="Linear program">linear program</a> (LP) is another LP that is derived from the original (the primal) LP in the following schematic way:

<ul><li>Each variable in the primal LP becomes a constraint in the dual LP;</li>

<li>Each constraint in the primal LP becomes a variable in the dual LP;</li>

<li>The objective direction is inversed – maximum in the primal becomes minimum in the dual and vice versa.</li></ul>

The weak duality theorem states that the objective value of the dual LP at any feasible solution is always a bound on the objective of the primal LP at any feasible solution (upper or lower bound, depending on whether it is a maximization or minimization problem). In fact, this bounding property holds for the optimal values of the dual and primal LPs.

The strong duality theorem states that, moreover, if the primal has an optimal solution then the dual has an optimal solution too, and the two optima are equal.<a href="#cite_note-gm06-1">[1]</a>

These theorems belong to a larger class of <a href="Duality_(optimization)" title="Duality (optimization)">duality theorems in optimization</a>. The strong duality theorem is one of the cases in which the <a href="Duality_gap" title="Duality gap">duality gap</a> (the gap between the optimum of the primal and the optimum of the dual) is 0.

Suppose we have the linear program: <blockquote>Maximize cTx subject to Ax ≤ b, x ≥ 0.</blockquote>We would like to construct an upper bound on the solution. So we create a linear combination of the constraints, with positive coefficients, such that the coefficients of x in the constraints are at least cT. This linear combination gives us an upper bound on the objective. The variables y of the dual LP are the coefficients of this linear combination. The dual LP tries to find such coefficients that minimize the resulting upper bound. This gives the following LP:<a href="#cite_note-gm06-1">[1]</a>: 81–83 <blockquote>Minimize bTy subject to ATy ≥ c, y ≥ 0 </blockquote>This LP is called the dual of the original LP.

<div class="mw-heading mw-heading3"><h3 id="Interpretation">Interpretation</h3></div>

The duality theorem has an economic interpretation.<a href="#cite_note-2">[2]</a><a href="#cite_note-3">[3]</a> If we interpret the primal LP as a classical "<a href="Resource_allocation" title="Resource allocation">resource allocation</a>" problem, its dual LP can be interpreted as a "resource valuation" problem.

Consider a factory that is planning its production of goods. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> be its production schedule (make <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"> amount of good <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">), let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\geq 0}</annotation>

</semantics>

</math><img src="./f5bacf524070fd3832229ef1b522442e3a2fb8e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.268ex; height:2.343ex;" alt="{\displaystyle c\geq 0}" loading="lazy"> be the list of market prices (a unit of good <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> can sell for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}}</annotation>

</semantics>

</math><img src="./01acb7953ba52c2aa44264b5d0f8fd223aa178a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.807ex; height:2.009ex;" alt="{\displaystyle c_{i}}" loading="lazy">). The constraints it has are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\geq 0}</annotation>

</semantics>

</math><img src="./a2608e2b392b079f5b763f27bf52883dbee3b64a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.591ex; height:2.343ex;" alt="{\displaystyle x\geq 0}" loading="lazy"> (it cannot produce negative goods) and raw-material constraints. Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> be the raw material it has available, and let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\geq 0}</annotation>

</semantics>

</math><img src="./ebee3e714a32508aa26658d5c88f6a09237c82dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.004ex; height:2.343ex;" alt="{\displaystyle A\geq 0}" loading="lazy"> be the matrix of material costs (producing one unit of good <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A_{ji}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A_{ji}}</annotation>

</semantics>

</math><img src="./e69838a00348145ea8766a36b8e398e5e8a810ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.22ex; height:2.843ex;" alt="{\displaystyle A_{ji}}" loading="lazy"> units of raw material <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy">).

Then, the constrained revenue maximization is the primal LP:<blockquote>Maximize cTx subject to Ax ≤ b, x ≥ 0.</blockquote>Now consider another factory that has no raw material, and wishes to purchase the entire stock of raw material from the previous factory. It offers a price vector of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"> (a unit of raw material <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"> for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}}</annotation>

</semantics>

</math><img src="./67d30d30b6c2dbe4d6f150d699de040937ecc95f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.939ex; height:2.009ex;" alt="{\displaystyle y_{i}}" loading="lazy">). For the offer to be accepted, it should be the case that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{T}y\geq c}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{T}y\geq c}</annotation>

</semantics>

</math><img src="./3cd2d5cd71075563526dec0bc6083c5c0bd9110f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.393ex; height:3.009ex;" alt="{\displaystyle A^{T}y\geq c}" loading="lazy">, since otherwise the factory could earn more cash by producing a certain product than selling off the raw material used to produce the good. It also should be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\geq 0}</annotation>

</semantics>

</math><img src="./130e8795bc869a5b823133c5a0972693605c00bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.416ex; height:2.509ex;" alt="{\displaystyle y\geq 0}" loading="lazy">, since the factory would not sell any raw material with negative price. Then, the second factory's optimization problem is the dual LP:<blockquote>Minimize bTy subject to ATy ≥ c, y ≥ 0</blockquote>The duality theorem states that the duality gap between the two LP problems is at least zero. Economically, it means that if the first factory is given an offer to buy its entire stock of raw material, at a per-item price of y, such that ATy ≥ c, y ≥ 0, then it should take the offer. It will make at least as much revenue as it could producing finished goods.

The strong duality theorem further states that the duality gap is zero. With strong duality, the dual solution <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y^{*}}</annotation>

</semantics>

</math><img src="./3fcfcfa0fbced647ea73759c68ffd7a028729d62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.215ex; height:2.676ex;" alt="{\displaystyle y^{*}}" loading="lazy"> is, economically speaking, the "equilibrium price" (see <a href="Shadow_price" title="Shadow price">shadow price</a>) for the raw material that a factory with production matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"> and raw material stock <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"> would accept for raw material, given the market price for finished goods <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math><img src="./86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy">. (Note that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y^{*}}</annotation>

</semantics>

</math><img src="./3fcfcfa0fbced647ea73759c68ffd7a028729d62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.215ex; height:2.676ex;" alt="{\displaystyle y^{*}}" loading="lazy"> may not be unique, so the equilibrium price may not be fully determined by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy">, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

To see why, consider if the raw material prices <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\geq 0}</annotation>

</semantics>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (A^{T}y)_{i}<c_{i}}</annotation>

</semantics>

</math><img src="./6c6280cbe6a0dbcb5822bcb21c75a4c2e9be4186.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.802ex; height:3.176ex;" alt="{\displaystyle (A^{T}y)_{i}<c_{i}}" loading="lazy"> for some <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">, then the factory would purchase more raw material to produce more of good <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy">, since the prices are "too low". Conversely, if the raw material prices satisfy <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A^{T}y\geq c,y\geq 0}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A^{T}y\geq c,y\geq 0}</annotation>

</semantics>

</math><img src="./570d9a08c5f0ab631f7e4c88419737be31267a1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.844ex; height:3.009ex;" alt="{\displaystyle A^{T}y\geq c,y\geq 0}" loading="lazy">, but does not minimize <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b^{T}y}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b^{T}y}</annotation>

</semantics>

</math><img src="./5462d71c0f5dbc65657a9ad3d544a901b9a09498.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.542ex; height:3.009ex;" alt="{\displaystyle b^{T}y}" loading="lazy">, then the factory would make more money by selling its raw material than producing goods, since the prices are "too high". At equilibrium price <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y^{*}}</annotation>

</semantics>

The duality theorem has a physical interpretation too.<a href="#cite_note-gm06-1">[1]</a>: 86–87

<div class="mw-heading mw-heading2"><h2 id="Constructing_the_dual_LP">Constructing the dual LP</h2></div>

In general, given a primal LP, the following algorithm can be used to construct its dual LP.<a href="#cite_note-gm06-1">[1]</a>: 85 The primal LP is defined by:

<ul><li>A set of n variables: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1},\ldots ,x_{n}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1},\ldots ,x_{n}}</annotation>

</semantics>

</math><img src="./737e02a5fbf8bc31d443c91025339f9fd1de1065.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.11ex; height:2.009ex;" alt="{\displaystyle x_{1},\ldots ,x_{n}}" loading="lazy">.</li>

<li>For each variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math><img src="./e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy">, a sign constraint – it should be either non-negative (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}\geq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}\geq 0}</annotation>

</semantics>

</math><img src="./90a99710f61d5dea19e49ae5b31164d2b56b07e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.39ex; height:2.509ex;" alt="{\displaystyle x_{i}\geq 0}" loading="lazy">), or non-positive (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}\leq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}\leq 0}</annotation>

</semantics>

</math><img src="./f8feb153376cf595bc9a797b3eb2429efd3c7605.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.39ex; height:2.509ex;" alt="{\displaystyle x_{i}\leq 0}" loading="lazy">), or unconstrained (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}\in \mathbb {R} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}\in \mathbb {R} }</annotation>

</semantics>

<li>An objective function: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}}">

<mtext>maximize</mtext>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}}</annotation>

</semantics>

</math><img src="./a410bc6e5194a496bfbff8a2d2bc09fea85f9632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:28.985ex; height:2.509ex;" alt="{\displaystyle {\text{maximize}}~~~c_{1}x_{1}+\cdots +c_{n}x_{n}}" loading="lazy"></li>

<li>A list of m constraints. Each constraint j is: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{j1}x_{1}+\cdots +a_{jn}x_{n}\lesseqqgtr b_{j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{j1}x_{1}+\cdots +a_{jn}x_{n}\lesseqqgtr b_{j}}</annotation>

</semantics>

</math><img src="./017c39e373499d8c229b8b1bfe5bf8f546e9a0f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:24.429ex; height:3.843ex;" alt="{\displaystyle a_{j1}x_{1}+\cdots +a_{jn}x_{n}\lesseqqgtr b_{j}}" loading="lazy">where the symbol before the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{j}}</annotation>

</semantics>

</math><img src="./fa56eff4488494085785b7b0d6e2069bd45a3ce5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:1.907ex; height:2.843ex;" alt="{\displaystyle b_{j}}" loading="lazy"> can be one of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \geq }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \geq }</annotation>

</semantics>

</math><img src="./bcef7c0e95bb77a35fd1a874ca91f425215f3c26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \geq }" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \leq }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \leq }</annotation>

</semantics>

</math><img src="./440568a09c3bfdf0e1278bfa79eb137c04e94035.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:1.808ex; height:2.176ex;" alt="{\displaystyle \leq }" loading="lazy"> or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle =}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle =}</annotation>

</semantics>

</math><img src="./505a4ceef454c69dffd23792c84b90f488543743.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: 0.307ex; margin-bottom: -0.478ex; width:1.808ex; height:1.343ex;" alt="{\displaystyle =}" loading="lazy">.</li></ul>

The dual LP is constructed as follows.

<ul><li>Each primal constraint becomes a dual variable. So there are m variables: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1},\ldots ,y_{m}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1},\ldots ,y_{m}}</annotation>

</semantics>

</math><img src="./5d5b339e24327c7f983d51cb2edaeba7905548f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.186ex; height:2.009ex;" alt="{\displaystyle y_{1},\ldots ,y_{m}}" loading="lazy">.</li>

<li>The sign constraint of each dual variable is "opposite" to the sign of its primal constraint. So "<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \geq b_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \geq b_{j}}</annotation>

</semantics>

</math><img src="./3b750068d4d8eda40a9835465922c68e6850cd4f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.361ex; height:2.843ex;" alt="{\displaystyle \geq b_{j}}" loading="lazy">" becomes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{j}\leq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{j}\leq 0}</annotation>

</semantics>

</math><img src="./1d36193050d9f06f4c6b8211249b1d5f557953fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.31ex; height:2.843ex;" alt="{\displaystyle y_{j}\leq 0}" loading="lazy"> and "<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \leq b_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \leq b_{j}}</annotation>

</semantics>

</math><img src="./c4d531e7ab7c6b721661762faeb769fbff1f74f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.361ex; height:2.843ex;" alt="{\displaystyle \leq b_{j}}" loading="lazy">" becomes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{j}\geq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{j}\geq 0}</annotation>

</semantics>

</math><img src="./49f3403ec2784b5cfb5dbb9f7672742464846410.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.31ex; height:2.843ex;" alt="{\displaystyle y_{j}\geq 0}" loading="lazy"> and "<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle =b_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle =b_{j}}</annotation>

</semantics>

</math><img src="./93df9304f366a3c290e62a6134f4197ee53b5ec4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:4.361ex; height:2.843ex;" alt="{\displaystyle =b_{j}}" loading="lazy">" becomes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{j}\in \mathbb {R} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{j}\in \mathbb {R} }</annotation>

</semantics>

</math><img src="./d426fb0c9e2292e5d7b476b7bcb78a1e6201ef40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.568ex; height:2.843ex;" alt="{\displaystyle y_{j}\in \mathbb {R} }" loading="lazy">.</li>

<li>The dual objective function is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}}">

<mtext>minimize </mtext>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}}</annotation>

</semantics>

</math><img src="./393d5cc936d27e123a76afb9560d115e10368fdb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:29.628ex; height:2.509ex;" alt="{\displaystyle {\text{minimize }}~~~b_{1}y_{1}+\cdots +b_{m}y_{m}}" loading="lazy"></li>

<li>Each primal variable becomes a dual constraint. So there are n constraints. The coefficient of a dual variable in the dual constraint is the coefficient of its primal variable in its primal constraint. So each constraint i is: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}}</annotation>

</semantics>

</math><img src="./56b94348c502b052c5124a184f851da0240df466.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:24.64ex; height:3.843ex;" alt="{\displaystyle a_{1i}y_{1}+\cdots +a_{mi}y_{m}\lesseqqgtr c_{i}}" loading="lazy">, where the symbol before the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c_{i}}</annotation>

</semantics>

</math><img src="./01acb7953ba52c2aa44264b5d0f8fd223aa178a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.807ex; height:2.009ex;" alt="{\displaystyle c_{i}}" loading="lazy"> is similar to the sign constraint on variable i in the primal LP. So <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}\leq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}\leq 0}</annotation>

</semantics>

</math><img src="./f8feb153376cf595bc9a797b3eb2429efd3c7605.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.39ex; height:2.509ex;" alt="{\displaystyle x_{i}\leq 0}" loading="lazy"> becomes "<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \leq c_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \leq c_{i}}</annotation>

</semantics>

</math><img src="./82acf0f6151a6a1ca6e31d8db473072621dbab58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.26ex; height:2.343ex;" alt="{\displaystyle \leq c_{i}}" loading="lazy">" and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}\geq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}\geq 0}</annotation>

</semantics>

</math><img src="./90a99710f61d5dea19e49ae5b31164d2b56b07e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.39ex; height:2.509ex;" alt="{\displaystyle x_{i}\geq 0}" loading="lazy"> becomes "<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \geq c_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \geq c_{i}}</annotation>

</semantics>

</math><img src="./7d4f47b3df3d9caf88cbd6c0ee3ef87187819045.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.26ex; height:2.343ex;" alt="{\displaystyle \geq c_{i}}" loading="lazy">" and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}\in \mathbb {R} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}\in \mathbb {R} }</annotation>

</semantics>

</math><img src="./c16c64c292c38a4a3ebfee3be0ade520d4463413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.648ex; height:2.509ex;" alt="{\displaystyle x_{i}\in \mathbb {R} }" loading="lazy"> becomes "<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle =c_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle =c_{i}}</annotation>

</semantics>

</math><img src="./9bdaa2ff7305f2116210502886a9dc620f313236.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.26ex; height:2.009ex;" alt="{\displaystyle =c_{i}}" loading="lazy">".</li></ul>

From this algorithm, it is easy to see that the dual of the dual is the primal.

<div class="mw-heading mw-heading2"><h2 id="Vector_formulations">Vector formulations</h2></div>

If all constraints have the same sign, it is possible to present the above recipe in a shorter way using matrices and vectors. The following table shows the relation between various kinds of primals and duals.

<th>Primal

</th>

<th>Dual

</th>

<th>Note

</th></tr>

<tr>

<td>Maximize cTx subject to Ax ≤ b, x ≥ 0

</td>

<td>Minimize bTy subject to ATy ≥ c, y ≥ 0

</td>

<td>This is called a "symmetric" dual problem

</td></tr>

<tr>

<td>Maximize cTx subject to Ax ≤ b

</td>

<td>Minimize bTy subject to ATy = c, y ≥ 0

</td>

<td>This is called an "asymmetric" dual problem

</td></tr>

<tr>

<td>Maximize cTx subject to Ax = b, x ≥ 0

</td>

<td>Minimize bTy subject to ATy ≥ c

</td>

<td>

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="The_duality_theorems">The duality theorems</h2></div>

Below, suppose the primal LP is "maximize cTx subject to [constraints]" and the dual LP is "minimize bTy subject to [constraints]".

<div class="mw-heading mw-heading3"><h3 id="Weak_duality">Weak duality</h3></div>

The weak duality theorem says that, for each feasible solution x of the primal and each feasible solution y of the dual: cTx ≤ bTy. In other words, the objective value in each feasible solution of the dual is an upper-bound on the objective value of the primal, and objective value in each feasible solution of the primal is a lower-bound on the objective value of the dual. Here is a proof for the primal LP "Maximize cTx subject to Ax ≤ b, x ≥ 0":

<li>= xTc [since this just a scalar product of the two vectors]</li>

<li>≤ xT(ATy) [since ATy ≥ c by the dual constraints, and x ≥ 0]</li>

<li>= (xTAT)y [by associativity]</li>

<li>= (Ax)Ty [by properties of transpose]</li>

<li>≤ bTy [since Ax ≤ b by the primal constraints, and y ≥ 0]</li></ul>

Weak duality implies:<blockquote>maxx cTx ≤ miny bTy</blockquote>In particular, if the primal is unbounded (from above) then the dual has no feasible solution, and if the dual is unbounded (from below) then the primal has no feasible solution.

<div class="mw-heading mw-heading3"><h3 id="Strong_duality">Strong duality</h3></div>

The strong duality theorem says that if one of the two problems has an optimal solution, so does the other one and that the bounds given by the weak duality theorem are tight, i.e.:<blockquote>maxx cTx = miny bTy</blockquote>The strong duality theorem is harder to prove; the proofs usually use the weak duality theorem as a sub-routine.

One proof uses the <a href="Simplex_algorithm" title="Simplex algorithm">simplex algorithm</a> and relies on the proof that, with the suitable pivot rule, it provides a correct solution. The proof establishes that, once the simplex algorithm finishes with a solution to the primal LP, it is possible to read from the final tableau, a solution to the dual LP. So, by running the simplex algorithm, we obtain solutions to both the primal and the dual simultaneously.<a href="#cite_note-gm06-1">[1]</a>: 87–89

Another proof uses the <a href="Farkas_lemma" class="mw-redirect" title="Farkas lemma">Farkas lemma</a>.<a href="#cite_note-gm06-1">[1]</a>: 94

<div class="mw-heading mw-heading3"><h3 id="Theoretical_implications">Theoretical implications</h3></div>

1. The weak duality theorem implies that finding a single feasible solution is as hard as finding an optimal feasible solution. Suppose we have an oracle that, given an LP, finds an arbitrary feasible solution (if one exists). Given the LP "Maximize cTx subject to Ax ≤ b, x ≥ 0", we can construct another LP by combining this LP with its dual. The combined LP has both x and y as variables:<blockquote>Maximize 1 </blockquote><blockquote>subject to Ax ≤ b, ATy ≥ c, cTx ≥ bTy, x ≥ 0, y ≥ 0</blockquote>If the combined LP has a feasible solution (x,y), then by weak duality, cTx = bTy. So x must be a maximal solution of the primal LP and y must be a minimal solution of the dual LP. If the combined LP has no feasible solution, then the primal LP has no feasible solution either.

2. The strong duality theorem provides a "good characterization" of the optimal value of an LP in that it allows us to easily prove that some value t is the optimum of some LP. The proof proceeds in two steps:<a href="#cite_note-lp-4">[4]</a>: 260–261

<ul><li>Show a feasible solution to the primal LP with value t; this proves that the optimum is at least t.</li>

<li>Show a feasible solution to the dual LP with value t; this proves that the optimum is at most t.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Tiny_example">Tiny example</h3></div>

Consider the primal LP, with two variables and one constraint:

<mtr>

<mtd>

<mtext>maximize </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{maximize }}&3x_{1}+4x_{2}\\{\text{subject to }}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{aligned}}}</annotation>

</semantics>

</math><img src="./8891be6a96fe5a75b68495620d70e0b90bff9fb3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.838ex; width:25.486ex; height:8.843ex;" alt="{\displaystyle {\begin{aligned}{\text{maximize }}&3x_{1}+4x_{2}\\{\text{subject to }}&5x_{1}+6x_{2}=7\\&x_{1}\geq 0,x_{2}\geq 0\end{aligned}}}" loading="lazy"></dd></dl>

Applying the recipe above gives the following dual LP, with one variable and two constraints:

<mtr>

<mtd>

<mtext>minimize </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<mtext>subject to </mtext>

</mrow>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\text{minimize }}&7y_{1}\\{\text{subject to }}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}}</annotation>

</semantics>

</math><img src="./9b530cabb1020508e426b44155448ce62718238a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -5.338ex; width:18.779ex; height:11.843ex;" alt="{\displaystyle {\begin{aligned}{\text{minimize }}&7y_{1}\\{\text{subject to }}&5y_{1}\geq 3\\&6y_{1}\geq 4\\&y_{1}\in \mathbb {R} \end{aligned}}}" loading="lazy"></dd></dl>

It is easy to see that the maximum of the primal LP is attained when x1 is minimized to its lower bound (0) and x2 is maximized to its upper bound under the constraint (7/6). The maximum is 4 ⋅ 7/6 = 14/3.

Similarly, the minimum of the dual LP is attained when y1 is minimized to its lower bound under the constraints: the first constraint gives a lower bound of 3/5 while the second constraint gives a stricter lower bound of 4/6, so the actual lower bound is 4/6 and the minimum is 7 ⋅ 4/6 = 14/3.

In accordance with the strong duality theorem, the maximum of the primal equals the minimum of the dual.

We use this example to illustrate the proof of the weak duality theorem. Suppose that, in the primal LP, we want to get an upper bound on the objective <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 3x_{1}+4x_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 3x_{1}+4x_{2}}</annotation>

</semantics>

</math><img src="./a1caeceeff173726920e2aa0c94cc479e77497d5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.933ex; height:2.509ex;" alt="{\displaystyle 3x_{1}+4x_{2}}" loading="lazy">. We can use the constraint multiplied by some coefficient, say <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}}</annotation>

</semantics>

</math><img src="./eef4db76d658a98219aca14df06d9869d2b43c42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.193ex; height:2.009ex;" alt="{\displaystyle y_{1}}" loading="lazy">. For any <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}}</annotation>

</semantics>

</math><img src="./eef4db76d658a98219aca14df06d9869d2b43c42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.193ex; height:2.009ex;" alt="{\displaystyle y_{1}}" loading="lazy"> we get: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}}</annotation>

</semantics>

</math><img src="./74aba805f2ac3811eb02cc3e6b34e5618f970235.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.069ex; height:2.843ex;" alt="{\displaystyle y_{1}\cdot (5x_{1}+6x_{2})=7y_{1}}" loading="lazy">. Now, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}\cdot 5x_{1}\geq 3x_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}\cdot 5x_{1}\geq 3x_{1}}</annotation>

</semantics>

</math><img src="./9ce886b762919a235a9e09645a9ee75479b9b18a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.064ex; height:2.509ex;" alt="{\displaystyle y_{1}\cdot 5x_{1}\geq 3x_{1}}" loading="lazy">and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}\cdot 6x_{2}\geq 4x_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}\cdot 6x_{2}\geq 4x_{2}}</annotation>

</semantics>

</math><img src="./a7870d9ca3e311b61db2b7c66578f856f988f0b4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.064ex; height:2.509ex;" alt="{\displaystyle y_{1}\cdot 6x_{2}\geq 4x_{2}}" loading="lazy">, then <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{1}\cdot (5x_{1}+6x_{2})\geq 3x_{1}+4x_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{1}\cdot (5x_{1}+6x_{2})\geq 3x_{1}+4x_{2}}</annotation>

</semantics>

</math><img src="./82dd2215c3047421ad75c8fb37fe69fd9267f433.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.647ex; height:2.843ex;" alt="{\displaystyle y_{1}\cdot (5x_{1}+6x_{2})\geq 3x_{1}+4x_{2}}" loading="lazy">, so <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 7y_{1}\geq 3x_{1}+4x_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 7y_{1}\geq 3x_{1}+4x_{2}}</annotation>

</semantics>

</math><img src="./fde2ff437c00c20c924ce4e4f9e7f009f0751813.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.388ex; height:2.509ex;" alt="{\displaystyle 7y_{1}\geq 3x_{1}+4x_{2}}" loading="lazy">. Hence, the objective of the dual LP is an upper bound on the objective of the primal LP.

<div class="mw-heading mw-heading3"><h3 id="Farmer_example">Farmer example</h3></div>

Consider a farmer who may grow wheat and barley with the set provision of some L land, F fertilizer and P pesticide.

To grow one unit of wheat, one unit of land, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{1}}</annotation>

</semantics>

</math><img src="./100c7fbf174fe8b06eacc2a6b0bb2e1badd1c7ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.549ex; height:2.509ex;" alt="{\displaystyle F_{1}}" loading="lazy"> units of fertilizer and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{1}}</annotation>

</semantics>

</math><img src="./398f438d75434e6fbf48dc232c1ad7228a738568.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{1}}" loading="lazy"> units of pesticide must be used. Similarly, to grow one unit of barley, one unit of land, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle F_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{2}}</annotation>

</semantics>

</math><img src="./0fd17e0779153d765b40ebef91533489b87b2e37.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.549ex; height:2.509ex;" alt="{\displaystyle F_{2}}" loading="lazy"> units of fertilizer and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{2}}</annotation>

</semantics>

</math><img src="./87858df7457aa93caaef5a316db87a7240cc8c29.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.547ex; height:2.509ex;" alt="{\displaystyle P_{2}}" loading="lazy"> units of pesticide must be used.

The primal problem would be the farmer deciding how much wheat (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}}</annotation>

</semantics>

</math><img src="./a8788bf85d532fa88d1fb25eff6ae382a601c308.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{1}}" loading="lazy">) and barley (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{2}}</annotation>

</semantics>

</math><img src="./d7af1b928f06e4c7e3e8ebfd60704656719bd766.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{2}}" loading="lazy">) to grow if their sell prices are <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}}</annotation>

</semantics>

</math><img src="./5bf84e7fd4fb8259a9b37f956afdf83ee2a020f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{2}}</annotation>

</semantics>

</math><img src="./1143e284d5f25cef778ab482edf6617a523ddd9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.479ex; height:2.509ex;" alt="{\displaystyle S_{2}}" loading="lazy"> per unit.

<table>

<td colspan="2">Maximize: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}</annotation>

</semantics>

</math><img src="./7dec056bd019a7cb780aba29201b6e2e68f2b89c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.925ex; height:2.509ex;" alt="{\displaystyle S_{1}\cdot x_{1}+S_{2}\cdot x_{2}}" loading="lazy">

</td>

<td>(maximize the revenue from producing wheat and barley)

</td></tr>

<tr>

<td>subject to:

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}+x_{2}\leq L}</annotation>

</semantics>

</math><img src="./6d67b19bb362ed9055a186d4480fa279ad37e6a7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.29ex; height:2.509ex;" alt="{\displaystyle x_{1}+x_{2}\leq L}" loading="lazy">

</td>

<td>(cannot use more land than available)

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F}</annotation>

</semantics>

</math><img src="./4ac3bb61bc71ac8c41a5163964ca10ffc9eef9ce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.903ex; height:2.509ex;" alt="{\displaystyle F_{1}\cdot x_{1}+F_{2}\cdot x_{2}\leq F}" loading="lazy">

</td>

<td>(cannot use more fertilizer than available)

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}</annotation>

</semantics>

</math><img src="./da5cc1437a98288e22b1af4f5502ceeeef4b54ac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.903ex; height:2.509ex;" alt="{\displaystyle P_{1}\cdot x_{1}+P_{2}\cdot x_{2}\leq P}" loading="lazy">

</td>

<td>(cannot use more pesticide than available)

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1},x_{2}\geq 0}</annotation>

</semantics>

</math><img src="./b668e0a1d484fae37d9d1375b63fdb0d4a38bf4f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.063ex; height:2.509ex;" alt="{\displaystyle x_{1},x_{2}\geq 0}" loading="lazy">

</td>

<td>(cannot produce negative quantities of wheat or barley).

</td></tr></tbody></table>

In matrix form this becomes:

<dl><dd>Maximize: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}">

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./9c476520119e4bf358d8ac36d1ebcd06f81fee69.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:14.916ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}S_{1}&S_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}}" loading="lazy"></dd>

<dd>subject to: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.}">

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.}</annotation>

</semantics>

</math><img src="./4b87340d4c1a4629eaa18ea5d9ff0cc140b0c4c9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:37.478ex; height:9.176ex;" alt="{\displaystyle {\begin{bmatrix}1&1\\F_{1}&F_{2}\\P_{1}&P_{2}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\leq {\begin{bmatrix}L\\F\\P\end{bmatrix}},\,{\begin{bmatrix}x_{1}\\x_{2}\end{bmatrix}}\geq 0.}" loading="lazy"></dd></dl>

For the dual problem assume that y unit prices for each of these means of production (inputs) are set by a planning board. The planning board's job is to minimize the total cost of procuring the set amounts of inputs while providing the farmer with a floor on the unit price of each of his crops (outputs), S1 for wheat and S2 for barley. This corresponds to the following LP:

<table>

<td colspan="2">Minimize: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}}</annotation>

</semantics>

</math><img src="./57a23c17cea8c64db190da3c5fa58ab13a20c203.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:23.486ex; height:2.509ex;" alt="{\displaystyle L\cdot y_{L}+F\cdot y_{F}+P\cdot y_{P}}" loading="lazy">

</td>

<td>(minimize the total cost of the means of production as the "objective function")

</td></tr>

<tr>

<td>subject to:

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{L}+F_{1}\cdot y_{F}+P_{1}\cdot y_{P}\geq S_{1}}</annotation>

</semantics>

</math><img src="./5a08eeae9272643319a9d990890619f07e222e52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:27.411ex; height:2.509ex;" alt="{\displaystyle y_{L}+F_{1}\cdot y_{F}+P_{1}\cdot y_{P}\geq S_{1}}" loading="lazy">

</td>

<td>(the farmer must receive no less than S1 for his wheat)

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{L}+F_{2}\cdot y_{F}+P_{2}\cdot y_{P}\geq S_{2}}</annotation>

</semantics>

</math><img src="./1dbdae94efeb1f67a837b7e7514cad7d7c78b6e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:27.411ex; height:2.509ex;" alt="{\displaystyle y_{L}+F_{2}\cdot y_{F}+P_{2}\cdot y_{P}\geq S_{2}}" loading="lazy">

</td>

<td>(the farmer must receive no less than S2 for his barley)

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{L},y_{F},y_{P}\geq 0}</annotation>

</semantics>

</math><img src="./10dcf0408b128856af87d724ae78314e1c4fbe71.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.028ex; height:2.509ex;" alt="{\displaystyle y_{L},y_{F},y_{P}\geq 0}" loading="lazy">

</td>

<td>(prices cannot be negative).

</td></tr></tbody></table>

In matrix form this becomes:

<dl><dd>Minimize: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}}">

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./25e6673756f03ae29069284d9d118444fedbf7f7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.171ex; width:18.217ex; height:9.509ex;" alt="{\displaystyle {\begin{bmatrix}L&F&P\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}}" loading="lazy"></dd>

<dd>subject to: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.}">

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.}</annotation>

</semantics>

</math><img src="./2936f36d2ec51b2a7980cd76c9aa1329ac582468.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.171ex; width:42.138ex; height:9.509ex;" alt="{\displaystyle {\begin{bmatrix}1&F_{1}&P_{1}\\1&F_{2}&P_{2}\end{bmatrix}}{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq {\begin{bmatrix}S_{1}\\S_{2}\end{bmatrix}},\,{\begin{bmatrix}y_{L}\\y_{F}\\y_{P}\end{bmatrix}}\geq 0.}" loading="lazy"></dd></dl>

The primal problem deals with physical quantities. With all inputs available in limited quantities, and assuming the unit prices of all outputs is known, what quantities of outputs to produce so as to maximize total revenue? The dual problem deals with economic values. With floor guarantees on all output unit prices, and assuming the available quantity of all inputs is known, what input unit pricing scheme to set so as to minimize total expenditure?

To each variable in the primal space corresponds an inequality to satisfy in the dual space, both indexed by output type. To each inequality to satisfy in the primal space corresponds a variable in the dual space, both indexed by input type.

The coefficients that bound the inequalities in the primal space are used to compute the objective in the dual space, input quantities in this example. The coefficients used to compute the objective in the primal space bound the inequalities in the dual space, output unit prices in this example.

Both the primal and the dual problems make use of the same matrix. In the primal space, this matrix expresses the consumption of physical quantities of inputs necessary to produce set quantities of outputs. In the dual space, it expresses the creation of the economic values associated with the outputs from set input unit prices.

Since each inequality can be replaced by an equality and a slack variable, this means each primal variable corresponds to a dual slack variable, and each dual variable corresponds to a primal slack variable. This relation allows us to speak about complementary slackness.

<div class="mw-heading mw-heading3"><h3 id="Infeasible_program">Infeasible program</h3></div>

A LP can also be unbounded or infeasible. Duality theory tells us that:

<ul><li>If the primal is unbounded, then the dual is infeasible;</li>

<li>If the dual is unbounded, then the primal is infeasible.</li></ul>

However, it is possible for both the dual and the primal to be infeasible. Here is an example:

<table>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2x_{1}-x_{2}}</annotation>

</semantics>

</math><img src="./bcc21cc02f5905be642d30e512e9fd4035b85583.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.771ex; height:2.509ex;" alt="{\displaystyle 2x_{1}-x_{2}}" loading="lazy">

</td></tr>

<tr>

<td>Subject to:

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}-x_{2}\leq 1}</annotation>

</semantics>

</math><img src="./ef1e5603823acdb9d4ea161db8a57c3ce10b7a2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.869ex; height:2.509ex;" alt="{\displaystyle x_{1}-x_{2}\leq 1}" loading="lazy">

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -x_{1}+x_{2}\leq -2}</annotation>

</semantics>

</math><img src="./e5cce22c98b0fccd9d9a8c2bdc764860fab33293.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.485ex; height:2.509ex;" alt="{\displaystyle -x_{1}+x_{2}\leq -2}" loading="lazy">

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1},x_{2}\geq 0.}</annotation>

</semantics>

</math><img src="./e4d859d9f2cc2136ea80a95eb549e167de96eaa2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.71ex; height:2.509ex;" alt="{\displaystyle x_{1},x_{2}\geq 0.}" loading="lazy">

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Viewing_the_solution_to_a_linear_programming_problem_as_a_(generalized)_eigenvector">Viewing the solution to a linear programming problem as a (generalized) eigenvector</h2></div>

There is a close connection between linear programming problems, eigenequations, and von Neumann's general equilibrium model. The solution to a linear programming problem can be regarded as a generalized eigenvector.

The eigenequations of a square matrix are as follows:

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} =\rho \mathbf {p} ^{T}\\\mathbf {A} \mathbf {z} =\rho {\mathbf {z} }\\\end{matrix}}}</annotation>

</semantics>

</math><img src="./9b977d9a5b4ac54be49e1c98b603e6f72f028c3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.295ex; margin-bottom: -0.21ex; width:12.82ex; height:6.176ex;" alt="{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} =\rho \mathbf {p} ^{T}\\\mathbf {A} \mathbf {z} =\rho {\mathbf {z} }\\\end{matrix}}}" loading="lazy">

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {p} ^{T}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {p} ^{T}}</annotation>

</semantics>

</math><img src="./c04de59dd4eed1b024ca6c492a67470a6ce628bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.875ex; height:3.009ex;" alt="{\displaystyle \mathbf {p} ^{T}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {z} }</annotation>

</semantics>

</math><img src="./82eca5d0928078d5a61b9e7e98cc73db31070909.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.188ex; height:1.676ex;" alt="{\displaystyle \mathbf {z} }" loading="lazy"> are the left and right eigenvectors of the square matrix <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {A} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {A} }</annotation>

</semantics>

</math><img src="./0795cc96c75d81520a120482662b90f024c9a1a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.019ex; height:2.176ex;" alt="{\displaystyle \mathbf {A} }" loading="lazy">, respectively, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \rho }</annotation>

</semantics>

</math><img src="./1f7d439671d1289b6a816e6af7a304be40608d64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.202ex; height:2.176ex;" alt="{\displaystyle \rho }" loading="lazy"> is the eigenvalue.

The above eigenequations for the square matrix can be extended to von Neumann's general equilibrium model:<a href="#cite_note-5">[5]</a>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} \geq \rho \mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} \mathbf {z} \leq \rho \mathbf {B} {\mathbf {z} }\\\end{matrix}}}</annotation>

</semantics>

</math><img src="./0dc21b634d89051291a2aa1a2c3fc1afe01ce2ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.295ex; margin-bottom: -0.21ex; width:14.722ex; height:6.176ex;" alt="{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} \geq \rho \mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} \mathbf {z} \leq \rho \mathbf {B} {\mathbf {z} }\\\end{matrix}}}" loading="lazy">

where the economic meanings of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {p} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {p} }</annotation>

</semantics>

</math><img src="./dd73e3862cb92b016721b8c492eadb4e8a577527.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.485ex; height:2.009ex;" alt="{\displaystyle \mathbf {p} }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {z} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {z} }</annotation>

</semantics>

</math><img src="./82eca5d0928078d5a61b9e7e98cc73db31070909.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.188ex; height:1.676ex;" alt="{\displaystyle \mathbf {z} }" loading="lazy"> are the equilibrium prices of various goods and the equilibrium activity levels of various economic agents, respectively.

The von Neumann's equilibrium model can be further extended to the following structural equilibrium model with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {A} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {A} }</annotation>

</semantics>

</math><img src="./0795cc96c75d81520a120482662b90f024c9a1a1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.019ex; height:2.176ex;" alt="{\displaystyle \mathbf {A} }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {B} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {B} }</annotation>

</semantics>

</math><img src="./cafb0ef39b0f5ffa23c170aa7f7b4e718327c4d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.901ex; height:2.176ex;" alt="{\displaystyle \mathbf {B} }" loading="lazy"> as matrix-valued functions:<a href="#cite_note-7">[7]</a>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\geq \rho \mathbf {p} ^{T}\mathbf {B} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\\\mathbf {A} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\mathbf {z} \leq \rho \mathbf {B} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} ){\mathbf {z} }\\\end{matrix}}}</annotation>

</semantics>

</math><img src="./99b5daaf6de272752fb894e94fa8b50f97961025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.374ex; margin-bottom: -0.297ex; width:30.793ex; height:6.509ex;" alt="{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\geq \rho \mathbf {p} ^{T}\mathbf {B} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\\\mathbf {A} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} )\mathbf {z} \leq \rho \mathbf {B} (\mathbf {p} ,\mathbf {u} ,\mathbf {z} ){\mathbf {z} }\\\end{matrix}}}" loading="lazy">

where the economic meaning of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {u} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {u} }</annotation>

</semantics>

</math><img src="./261e20fe101de02a771021d9d4466c0ad3e352d7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.485ex; height:1.676ex;" alt="{\displaystyle \mathbf {u} }" loading="lazy"> is the utility levels of various consumers. A special case of the above model is

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (u)\geq \mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} (u)\mathbf {z} \leq \mathbf {B} {\mathbf {z} }\end{matrix}}}</annotation>

</semantics>

</math><img src="./761bfc8d7d2401265d6a0997585cb14e877e1948.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.374ex; margin-bottom: -0.297ex; width:16.659ex; height:6.509ex;" alt="{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (u)\geq \mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} (u)\mathbf {z} \leq \mathbf {B} {\mathbf {z} }\end{matrix}}}" loading="lazy">

This form of the structural equilibrium model and linear programming problems can often be converted to each other, that is, the solutions to these two types of problems are often consistent.

If we define

</mrow>

<mrow>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {A} (u)={\begin{bmatrix}\mathbf {0} &u\\\mathbf {A} &\mathbf {0} \\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./c301fe6c37607030452a9349bfc89bfb8b8956b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:17.142ex; height:6.176ex;" alt="{\displaystyle \mathbf {A} (u)={\begin{bmatrix}\mathbf {0} &u\\\mathbf {A} &\mathbf {0} \\\end{bmatrix}}}" loading="lazy">,

</mrow>

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {B} ={\begin{bmatrix}\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {b} \\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./733b5a2b04b9f44425a99ebd38f7ead9f672b1a6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:14.591ex; height:6.176ex;" alt="{\displaystyle \mathbf {B} ={\begin{bmatrix}\mathbf {c} ^{T}&0\\\mathbf {0} &\mathbf {b} \\\end{bmatrix}}}" loading="lazy">,

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {p} ={\begin{bmatrix}1\\\mathbf {y} \\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./598a65ed8d5c2e8e9e0c62a17d6f7860179fbac6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:9.201ex; height:6.176ex;" alt="{\displaystyle \mathbf {p} ={\begin{bmatrix}1\\\mathbf {y} \\\end{bmatrix}}}" loading="lazy">,

</mrow>

<mrow>

<mtr>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {z} ={\begin{bmatrix}\mathbf {x} \\1\\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./f15f7452f56918bf13534e55128339f2d3d9014a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:8.904ex; height:6.176ex;" alt="{\displaystyle \mathbf {z} ={\begin{bmatrix}\mathbf {x} \\1\\\end{bmatrix}}}" loading="lazy">, then the structural equilibrium model can be written as

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mtd>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}\mathbf {y} ^{T}\mathbf {A} &u\\\end{bmatrix}}\geq {\begin{bmatrix}\mathbf {c} ^{T}&\mathbf {y} ^{T}\mathbf {b} \\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./c00dcbf5132be43058c70a1426b576f1dfb9283e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.846ex; height:2.843ex;" alt="{\displaystyle {\begin{bmatrix}\mathbf {y} ^{T}\mathbf {A} &u\\\end{bmatrix}}\geq {\begin{bmatrix}\mathbf {c} ^{T}&\mathbf {y} ^{T}\mathbf {b} \\\end{bmatrix}}}" loading="lazy">

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{bmatrix}u\\\mathbf {A} \mathbf {x} \\\end{bmatrix}}\leq {\begin{bmatrix}\mathbf {c} ^{T}\mathbf {x} \\\mathbf {b} \\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./19354b1ea07b2bacd9b6ed46a26071a224b3ce42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:16.93ex; height:6.176ex;" alt="{\displaystyle {\begin{bmatrix}u\\\mathbf {A} \mathbf {x} \\\end{bmatrix}}\leq {\begin{bmatrix}\mathbf {c} ^{T}\mathbf {x} \\\mathbf {b} \\\end{bmatrix}}}" loading="lazy">

Let us illustrate the structural equilibrium model with the previously discussed tiny example. In this example, we have

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {A} ={\begin{bmatrix}5&6\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./c495ae25f42eba060ef913c64fa57f55d7d13307.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.811ex; height:2.843ex;" alt="{\displaystyle \mathbf {A} ={\begin{bmatrix}5&6\end{bmatrix}}}" loading="lazy">,

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {A} (u)={\begin{bmatrix}0&0&u\\5&6&0\\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./459615963d3da84f1948d83536d827849d815fe7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:19.763ex; height:6.176ex;" alt="{\displaystyle \mathbf {A} (u)={\begin{bmatrix}0&0&u\\5&6&0\\\end{bmatrix}}}" loading="lazy"> and

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {B} ={\begin{bmatrix}3&4&0\\0&0&7\\\end{bmatrix}}}</annotation>

</semantics>

</math><img src="./25b96d11389467d6e62d615a8bdf87074b69b152.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:16.338ex; height:6.176ex;" alt="{\displaystyle \mathbf {B} ={\begin{bmatrix}3&4&0\\0&0&7\\\end{bmatrix}}}" loading="lazy">.

To solve the structural equilibrium model, we obtain

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {p} ^{*}=(1,2/3)^{T},\quad \mathbf {z} ^{*}=(0,7/6,1)^{T},\quad u^{*}=14/3}</annotation>

</semantics>

</math><img src="./e2a21ad28100275f6c07c3a8fb69478d7de0ebbe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:47.785ex; height:3.176ex;" alt="{\displaystyle \mathbf {p} ^{*}=(1,2/3)^{T},\quad \mathbf {z} ^{*}=(0,7/6,1)^{T},\quad u^{*}=14/3}" loading="lazy">

These are consistent with the solutions to the linear programming problems.

We substitute the above calculation results into the structural equilibrium model, obtaining

<mtr>

<mtd>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (u)=(10/3,4,14/3)\geq (3,4,14/3)=\mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} (u)\mathbf {z} =(14/3,7)^{T}\leq (14/3,7)^{T}=\mathbf {B} {\mathbf {z} }\end{matrix}}}</annotation>

</semantics>

</math><img src="./d89aa4111761170c3b20dfbd53e16f77d90e5ecc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:48.047ex; height:6.509ex;" alt="{\displaystyle {\begin{matrix}\mathbf {p} ^{T}\mathbf {A} (u)=(10/3,4,14/3)\geq (3,4,14/3)=\mathbf {p} ^{T}\mathbf {B} \\\mathbf {A} (u)\mathbf {z} =(14/3,7)^{T}\leq (14/3,7)^{T}=\mathbf {B} {\mathbf {z} }\end{matrix}}}" loading="lazy">

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

The max-flow min-cut theorem is a special case of the strong duality theorem: flow-maximization is the primal LP, and cut-minimization is the dual LP. See <a href="Max-flow_min-cut_theorem#Linear_program_formulation" title="Max-flow min-cut theorem">Max-flow min-cut theorem#Linear program formulation</a>.

Other graph-related theorems can be proved using the strong duality theorem, in particular, <a href="Konig's_theorem_(graph_theory)" class="mw-redirect" title="Konig's theorem (graph theory)">Konig's theorem</a>.<a href="#cite_note-9">[9]</a>

The <a href="Minimax_theorem" title="Minimax theorem">Minimax theorem</a> for zero-sum games can be proved using the strong-duality theorem.<a href="#cite_note-gm06-1">[1]</a>: sub.8.1

<div class="mw-heading mw-heading2"><h2 id="Alternative_algorithm">Alternative algorithm</h2></div>

Sometimes, one may find it more intuitive to obtain the dual program without looking at the program matrix. Consider the following linear program:

<td>Minimize

</td>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}}</annotation>

</semantics>

</math><img src="./575efa0127d3546f7116b248e876777fafb523ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:18.128ex; height:7.176ex;" alt="{\displaystyle \sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}}" loading="lazy">

</td></tr>

<tr>

<td>subject to

</td>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{m}a_{ij}x_{i}+e_{j}t_{j}\geq g_{j},}</annotation>

</semantics>

</math><img src="./779b2160bd8e1eb1dace12579ca90d671ecc304b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:20.925ex; height:6.843ex;" alt="{\displaystyle \sum _{i=1}^{m}a_{ij}x_{i}+e_{j}t_{j}\geq g_{j},}" loading="lazy">

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq j\leq n}</annotation>

</semantics>

</math><img src="./829066d1e818107baff629179da368c45fcb8883.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.712ex; height:2.509ex;" alt="{\displaystyle 1\leq j\leq n}" loading="lazy">

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{i}x_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\geq h_{i},}</annotation>

</semantics>

</math><img src="./6bbcac839da194ce5875898de2077f46a5f1fba1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:20.759ex; height:7.176ex;" alt="{\displaystyle f_{i}x_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\geq h_{i},}" loading="lazy">

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq m}</annotation>

</semantics>

</math><img src="./be7492673ec3919cb5774b3ba4bb81a7c2365c88.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:10.202ex; height:2.343ex;" alt="{\displaystyle 1\leq i\leq m}" loading="lazy">

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}\geq 0,\,t_{j}\geq 0,}</annotation>

</semantics>

</math><img src="./278e360594f558676bcc6d738fb3c104f4931d17.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.468ex; height:2.843ex;" alt="{\displaystyle x_{i}\geq 0,\,t_{j}\geq 0,}" loading="lazy">

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq m,1\leq j\leq n}</annotation>

</semantics>

</math><img src="./f5e42ea3c962b5cd516529d361cfa5d073c38f8d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.948ex; height:2.509ex;" alt="{\displaystyle 1\leq i\leq m,1\leq j\leq n}" loading="lazy">

</td></tr></tbody></table>

We have m + n conditions and all variables are non-negative. We shall define m + n dual variables: yj and si. We get:

<td>Minimize

</td>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{m}c_{i}x_{i}+\sum _{j=1}^{n}d_{j}t_{j}}</annotation>

</semantics>

</td></tr>

<tr>

<td>subject to

</td>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{i=1}^{m}a_{ij}x_{i}\cdot y_{j}+e_{j}t_{j}\cdot y_{j}\geq g_{j}\cdot y_{j},}</annotation>

</semantics>

</math><img src="./e155389091813026e56f100fba9aa2bcd82754bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:32.11ex; height:6.843ex;" alt="{\displaystyle \sum _{i=1}^{m}a_{ij}x_{i}\cdot y_{j}+e_{j}t_{j}\cdot y_{j}\geq g_{j}\cdot y_{j},}" loading="lazy">

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq j\leq n}</annotation>

</semantics>

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f_{i}x_{i}\cdot s_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\cdot s_{i}\geq h_{i}\cdot s_{i},}</annotation>

</semantics>

</math><img src="./951397c643f502153878f3e9fb675c3a28972119.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:31.466ex; height:7.176ex;" alt="{\displaystyle f_{i}x_{i}\cdot s_{i}+\sum _{j=1}^{n}b_{ij}t_{j}\cdot s_{i}\geq h_{i}\cdot s_{i},}" loading="lazy">

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq m}</annotation>

</semantics>

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}\geq 0,\,t_{j}\geq 0,}</annotation>

</semantics>

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq m,1\leq j\leq n}</annotation>

</semantics>

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{j}\geq 0,\,s_{i}\geq 0,}</annotation>

</semantics>

</math><img src="./1de158b2e3204f6860048f50ba29a7aa165449a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:14.529ex; height:2.843ex;" alt="{\displaystyle y_{j}\geq 0,\,s_{i}\geq 0,}" loading="lazy">

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq j\leq n,1\leq i\leq m}</annotation>

</semantics>

</math><img src="./89a72c78f95b605681c9ca97557fd66e42638363.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:20.948ex; height:2.509ex;" alt="{\displaystyle 1\leq j\leq n,1\leq i\leq m}" loading="lazy">

</td></tr></tbody></table>

Since this is a minimization problem, we would like to obtain a dual program that is a lower bound of the primal. In other words, we would like the sum of all right hand side of the constraints to be the maximal under the condition that for each primal variable the sum of its <a href="Coefficient" title="Coefficient">coefficients</a> do not exceed its coefficient in the linear function. For example, x1 appears in n + 1 constraints. If we sum its constraints' coefficients we get a1,1y1 + a1,2y2 + ... + a1,;;n;;yn + f1s1. This sum must be at most c1. As a result, we get:

<td>Maximize

</td>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{j=1}^{n}g_{j}y_{j}+\sum _{i=1}^{m}h_{i}s_{i}}</annotation>

</semantics>

</math><img src="./81c23cdbec10f8d916fb38dcca4212050096803a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:18.421ex; height:7.176ex;" alt="{\displaystyle \sum _{j=1}^{n}g_{j}y_{j}+\sum _{i=1}^{m}h_{i}s_{i}}" loading="lazy">

</td></tr>

<tr>

<td>subject to

</td>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{j=1}^{n}a_{ij}y_{j}+f_{i}s_{i}\leq c_{i},}</annotation>

</semantics>

</math><img src="./03478cac5c019d6d2fb949809d0217a821d4562b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:20.719ex; height:7.176ex;" alt="{\displaystyle \sum _{j=1}^{n}a_{ij}y_{j}+f_{i}s_{i}\leq c_{i},}" loading="lazy">

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq i\leq m}</annotation>

</semantics>

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e_{j}y_{j}+\sum _{i=1}^{m}b_{ij}s_{i}\leq d_{j},}</annotation>

</semantics>

</math><img src="./623565c7aadea7447d6ac4777b3f53e1eea0afef.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:20.853ex; height:6.843ex;" alt="{\displaystyle e_{j}y_{j}+\sum _{i=1}^{m}b_{ij}s_{i}\leq d_{j},}" loading="lazy">

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq j\leq n}</annotation>

</semantics>

</td></tr>

<tr>

<td>

</td>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{j}\geq 0,\,s_{i}\geq 0,}</annotation>

</semantics>

</td>

<td>

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\leq j\leq n,1\leq i\leq m}</annotation>

</semantics>

</td></tr></tbody></table>

Note that we assume in our calculations steps that the program is in standard form. However, any linear program may be transformed to standard form and it is therefore not a limiting factor.

<ul><li><a href="Convex_duality" class="mw-redirect" title="Convex duality">Convex duality</a></li>

<li><a href="Duality_(mathematics)" title="Duality (mathematics)">Duality</a></li>

<li><a href="Duality_(optimization)" title="Duality (optimization)">Duality (optimization)</a></li>

<li><a href="Semidefinite_programming" title="Semidefinite programming">Semidefinite programming</a></li>

<li><a href="Relaxation_(approximation)" title="Relaxation (approximation)">Relaxation (approximation)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGärtnerMatoušek2006" class="citation book cs1">Gärtner, Bernd; <a href="Ji%C5%99%C3%AD_Matou%C5%A1ek_(mathematician)" title="Jiří Matoušek (mathematician)">Matoušek, Jiří</a> (2006). Understanding and Using Linear Programming. Berlin: Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-30697-8</bdi>.</cite> Pages 81–104.

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFSakarovitch1983" class="citation cs2">Sakarovitch, Michel (1983), <a rel="nofollow" class="external text" href="https://dx.doi.org/10.1007/978-1-4757-4106-3_9">Complements on Duality: Economic Interpretation of Dual Variables</a>, Springer Texts in Electrical Engineering, New York, NY: Springer New York, pp. 142–155, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-1-4757-4106-3_9">10.1007/978-1-4757-4106-3_9</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-90829-8</bdi>, retrieved 2022-12-23</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFDorfman1987" class="citation book cs1">Dorfman, Robert (1987). Linear programming and economic analysis. Paul A. Samuelson, Robert M. Solow. New York: Dover Publications. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-486-65491-5</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/16577541">16577541</a>.</cite>

</li>

<li id="cite_note-lp-4"><a href="#cite_ref-lp_4-0">^</a> <cite id="CITEREFLovászPlummer1986" class="citation cs2"><a href="L%C3%A1szl%C3%B3_Lov%C3%A1sz" title="László Lovász">Lovász, László</a>; <a href="Michael_D._Plummer" title="Michael D. Plummer">Plummer, M. D.</a> (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-444-87916-1</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0859549">0859549</a></cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFvon_Neumann1945" class="citation journal cs1">von Neumann, J. (1945). "A Model of General Economic Equilibrium". The Review of Economic Studies. 13: 1–9.</cite>:

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFKemenyMorgensternThompson1956" class="citation journal cs1">Kemeny, J. G.; Morgenstern, O.; Thompson, G. L. (1956). "A Generalization of the von Neumann Model of an Expanding Economy". Econometrica. 24: 115–135.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFLi2019" class="citation book cs1 cs1-prop-foreign-lang-source">Li, Wu (2019). General Equilibrium and Structural Dynamics: Perspectives of New Structural Economics (in Chinese). Beijing: Economic Science Press. pp. 122–125. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-7-5218-0422-5</bdi>.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://search.r-project.org/CRAN/refmans/GE/html/gemDualLinearProgramming.html">"General Equilibrium Model and Dual Linear Program"</a>. CRAN - R Project. Retrieved 2023-06-26. <q>Detailed documentation on the General Equilibrium Model and Dual Linear Program in R.</q></cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFA._A._Ahmadi2016" class="citation web cs1">A. A. Ahmadi (2016). <a rel="nofollow" class="external text" href="http://www.princeton.edu/~amirali/Public/Teaching/ORF523/S16/ORF523_S16_Lec6_gh.pdf">"Lecture 6: linear programming and matching"</a> (PDF). Princeton University.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-21" href="https://en.wikipedia.org/wiki/?title=Dual_linear_program&oldid=1301708161">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>